import math

def swap_element(sequence, left, right):
    sequence[left], sequence[right] = sequence[right], sequence[left]

class max_heap(object):
    __slots__ = ('heap_length', 'array')

    def __init__(self, array):
        self.heap_length = len(array)
        self.array = array

        last_non_leaf = int(math.floor(self.heap_length / 2)) - 1
        non_leaf = last_non_leaf
        while non_leaf >= 0:
            self.max_heapify(non_leaf)
            non_leaf -= 1

    def first_leaf(self):
        return int(math.floor(self.heap_length / 2))

    @staticmethod
    def parent(index):
        assert isinstance(index, int)
        assert index > 0
        return int(math.floor((index + 1) / 2)) - 1

    @staticmethod
    def left_child(index):
        assert isinstance(index, int)
        return (index + 1) * 2 - 1

    @staticmethod
    def right_child(index):
        assert isinstance(index, int)
        return (index + 1) * 2

    def max_heapify(self, parent):
        first_leaf = self.first_leaf()

        while parent < first_leaf:
            left_child = max_heap.left_child(parent)
            right_child = max_heap.right_child(parent)
            max = parent
            if left_child < self.heap_length and self.array[left_child] > self.array[parent]:
                max = left_child
            if right_child < self.heap_length and self.array[right_child] > self.array[max]:
                max = right_child
            
            if max != parent:
                swap_element(self.array, parent, max)
                parent = max
            else:
                break

        return self.array

